\documentclass[a4paper,10pt]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{times}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}
\definecolor{gray97}{gray}{.97}
\definecolor{gray75}{gray}{.75}
\definecolor{gray45}{gray}{.45}
\usepackage{listings}
\lstset{ frame=Ltb,
 framerule=0pt,
 aboveskip=0.5cm,
 framextopmargin=3pt,
 framexbottommargin=3pt,
 framexleftmargin=0.4cm,
 framesep=0pt,
 rulesep=.4pt,
 backgroundcolor=\color{gray97},
 rulesepcolor=\color{black},
 stringstyle=\ttfamily,
 showstringspaces = false,
 basicstyle=\small\ttfamily,
 commentstyle=\color{gray45},
 keywordstyle=\bfseries,
 numbers=left,
 numbersep=15pt,
 numberstyle=\tiny,
 numberfirstline = false,
 breaklines=true,
}
\lstnewenvironment{listing}[1][]
{\lstset{#1}\pagebreak[0]}{\pagebreak[0]}
\lstdefinestyle{consola}
{basicstyle=\scriptsize\bf\ttfamily,
backgroundcolor=\color{gray75},
}
\lstdefinestyle{C}
 {language=C,
}
\begin{document}
\rmfamily
\pagestyle{fancy} 
\thispagestyle{empty} 
\begin{center}
\begin{Huge}
\textbf{Trabajo Pr\'actico 0\\}
\end{Huge}
\end{center}
\begin{center}
\begin{LARGE}
Rafael Putaro, 84236\\
rafaelputaro@yahoo.com.ar\\
\hspace{15mm}
\end{LARGE}
\end{center}
\begin{center}
2 do. Cuatrimestre de 2012\\
66.20 Organizaci\'on de Computadoras\\
Facultad de Ingenier\'a, Universidad de Buenos Aires\\
\end{center}
\hspace{15mm}
\begin{small}
\begin{center}
Resumen\\
\end{center}
\hspace{4mm}En el presente trabajo pr\'actico se intenta tomar contactos con las herramientas que se utilizar\'an en el curso. Para lograr dicho objetivo se tomaron una serie de mediciones de tiempos de procesamiento sobre muestras de diferentes tama\~nos con dos algoritmos de ordenamiento diferentes, cuyos ordenes son distintos. Los resultados obtenidos son evaluados y documentados mediante las herramientas propuestas.\\
\newpage  
\end{small}
\section{Introducci\'on}
\begin{normalsize}
Mediante la utilización de las herramientas provistas por la cátedra se estudiará el desempeño de dos algoritmos de ordenamiento de diferente orden.
Dichos algoritmos son el Merge Sort y el Selection Sort, los cuales se implementarán en C, y se evaluará su desempeño por medio de las herramientas gprof y time.
La evaluación consistirá en testear el desempeño de los mismos por medio de entradas de diferente tamaño.
Los datos obtenidos serán analizados por medio de la estadística, gráficos y la Ley de Amdahl.\\
El análisis de los resultados permitirá tomar contacto con herramientas para la evaluación de desempeño de software y observar detalladamente cuales son los aspectos que hacen al rendimiento de una aplicación.\\
\end{normalsize}
\newpage 
\section{Implementaci\'on de algoritmos}
\begin{normalsize}
Se implementaron los algoritmos de ordenamiento ``merge sort'' y ``selection sort'' en C.
El problema fue abordado mediante la divisi\'on del c\'odigo en 3 secciones:
\begin{enumerate}
\item Main: Dado por el archivo ``tp06620.c'' que contiene la funci\'on main que recibe los par\'ametros para la ejecuci\'on del programa y llama a la funci\'on de procesamiento de argumentos.
\item Procesamiento de argumentos: Cuyas funciones son declaradas en el archivo ``ProcesamientoArgumentos.h'' e implementadas en el archivo ``ProcesamientoArgumentos.c''. Esta secci\'on se encarga de determinar, a partir de los argumentos del main, si se debe realizar un ordenamiento (en ese caso de que tipo) o se debe presentar alguna clase de informaci\'on acerca del programa. Una vez determinado lo que se debe realizar redirige el flujo del programa para hacer efectivo lo solicitado.
\item Ordenamiento: Cuyas funciones son declaradas en el archivo ``Ordenamiento.h'' y son implementadas en el archivo ``Ordenamiento.c''. Implementa los algoritmos merge y selection sort.
\end{enumerate}
El dise\~no del programa responde al siguiente diagrama, donde se han representado las funciones declaradas en el header como p\'ublicas, y las que han sido declaradas en el archivo fuente como privadas:\\
\end{normalsize}
\begin{figure}[hbtp]
\centering
\includegraphics[width=340pt , height=135pt]{ordenamiento.png} 
\end{figure}
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=135pt]{ProcesamientoArgumentos.png} 
\end{figure}
\newpage 
\begin{normalsize}
Se representa una corrida t\'ipica del programa mediante el siguiente diagrama de secuencia:\\
\end{normalsize}
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=465pt]{diagramaEjecucion.png} 
\end{figure}
\newpage 
\section{Compilaci\'on}
\begin{normalsize}
Para la compilac\'on del programa se debe utilizar el siguiente comando desde el directorio d\'onde se encuentran los archivos fuente:	\\
\begin{center}
gcc -Wall -O0 tp06620.c  ProcesamientoArgumentos.c  Ordenamiento.c -o tp\\
\end{center}
\textbf{Nota: }Se deber\'ian copiar previamente los archivos ``tp06620.c'', ``ProcesamientoArgumentos.h'', ``ProcesamientoArgumentos.c'', ``Ordenamiento.h'' y ``Ordenamiento.c'' desde el CD a un disco r\'igido.\\
\newpage
\end{normalsize}
\section{Resultado de las mediciones}
\begin{normalsize}
Para automatizar la obtenci\'on de los tiempos de procesamientos de ambos algoritmos, con diferentes tamaños de entrada, se escribi\i'o un script dado por el archivo ``medici\'on.sh''. Dicho script generó un archivo con los tiempos para cada uno de los algoritmos.\\
Las corridas completas con los archivos generados por el script se encuentran en el ``Anexo mediciones'', aqu\'i se presentar\'an los resultados en forma compacta mediante las siguientes tablas:\\
\end{normalsize}
\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=180pt]{mergesorttablas.png} 
\caption{Merge Sort}
\centering
\includegraphics[width=300pt , height=180pt]{selectionsorttablas.png} 
\caption{Selection Sort}
\begin{small}
\begin{flushleft}
\textbf{Nota: En el caso del ``selection sort'' los tiempos para las entradas m\'as grandes fueron deducidos, ya que se llego a un punto donde ordenar cada uno de los archivos requer\'ia horas.\\}
\end{flushleft}
\end{small}
\end{figure}
\newpage
\section{Representaci\'on gr\'afica de las mediciones}
\begin{normalsize}
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=180pt]{mergesort10archivos.png} 
\caption{Merge Sort 10 arrays aleatorios}	
\end{figure}
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=180pt]{mergesortarrayordenado.png} 
\caption{Merge Sort array ordenado}	
\end{figure}
\newpage
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=180pt]{mergesortarrayordenadoinverso.png} 
\caption{Merge Sort array ordenado inversamente}	
\end{figure}
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=180pt]{selectionsort10arrays.png} 
\caption{Selection Sort 10 arrays aleatorios}	
\end{figure}
\newpage
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=180pt]{selectionsortarrayordenado.png} 
\caption{Selection Sort array ordenado}	
\end{figure}
\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=180pt]{selectionsortarrayinverso.png} 
\caption{Selection Sort array ordenado inversamente}	
\end{figure}
\end{normalsize}
\newpage
\section{An\'alisis de las mediciones}
\begin{normalsize}
Al revisar los gráficos obtenidos se puede observar, como era de esperarse, que ambos algoritmos demoran más tiempo en ordenar a medida que las entradas son más grandes.
Al observar la Figura 9 se puede apreciar el orden superior del Merge Sort sobre Selection Sort, al ordenar una serie de entradas aleatorias, ya que este último presenta un disparo en el tiempo consumido al superar los 10K, mientras que para Merge Sort el disparo ocurre mucho después.\\
\end{normalsize}
\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=150pt]{mergesortselectionsor1.png} 
\caption{Merge Sort vs Selection Sort (10 arrays) bytes}
\end{figure}
\begin{normalsize}
\linebreak 
Aún para el caso de un array ordenado el Selection Sort dispará sus tiempos rápidamente, como puede observarse en la Figura 10.\\
\end{normalsize}

\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=150pt]{mergesortselectionsort3.png} 
\caption{Merge Sort vs Selection Sort (array ordenado)}
\end{figure}
\begin{normalsize}
En el caso de un array ordenado inversamente presenta el mismo comportamiento que en el primer caso, lo cual puede observarse en la Figura 11.\\
\end{normalsize}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=150pt]{mergesortselectionsort2.png} 
\caption{Merge Sort vs Selection Sort (array ordenado inverso)}
\end{figure}

\begin{normalsize}
Si para los tres casos calculamos el Speed Up logrado usando como tiempos viejos los obtenidos con el Selection Sort y como tiempos mejorados los obtenidos con el Merge Sort obtenemos los gráficos de las Figuras 12, 13 y 14.

$$SpeedUp_{global}=\frac{T_{selection}}{T_{merge}} $$
\end{normalsize}

\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=150pt]{speedupglobal10arrays.png} 
\caption{SpeedUp logrado tomando el promedio de tiempos de 10 arrays aleatorios}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=150pt]{speeduparrayordenado.png} 
\caption{SpeedUp logrado ordenando un array ordenado}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=150pt]{speeduparrayordenadoinverso.png} 
\caption{SpeedUp logrado ordenando un array ordenado inversamente}
\end{figure}

\begin{normalsize}
De los tres gráficos y las tablas podemos concluir que con archivos de hasta 800 bytes es indistinto usar uno u otro algoritmo. Si a partir de 800 bytes nos movemos hacia tamaños mayores el Merge Sort mejora rápidamente los tiempos, llegando a un SpeedUp de 500 al alcanzar a los 100K.
\end{normalsize}

\newpage

\section{Profiling}
\begin{normalsize}
Se desea averiguar como mejorar el desempeño del programa al ordenar por Selection Sort, por lo tanto se realiza un análisis de tiempos sobre las funciones del programa con la herramienta gprof.\\
Al probar entradas de diferente tamaños se determinó que el programa pasa la mayoría del tiempo en la función selectionSort, arrojando porcentajes del cero porciento para el resto de las funciones.\\
Por lo tanto se decide utilizar una entrada de tamaño bastante grande para calcular el porcentaje de tiempo que pasa el programa en la función selectionSort por medio de los tiempos acumulados.\\
De esta manera se decidió correr el programa con una entrada de 409600 bytes como se puede observar en la Figura 15.\\
\linebreak 
\end{normalsize}
\begin{figure}[hbtp]
\centering
\includegraphics[width=300pt , height=150pt]{profile.png} 
\caption{Profile de ejecución del programa sobre un array random de 409600 bytes}
\end{figure}
\linebreak 
\begin{normalsize}
Como se puede observar en la Figura 15 se logró una cierta acumulación de milisegundos en la función cargarDatosDesdeArchivo, lo cual esta directamente asociado a la utilización de una entrada grande.\\
De está manera se tiene un tiempo total de 348,28 segundos y un tiempo de 348,27 segundos en la función selectionSort.\\
Con está información nos alcanza para realizar los siguientes cálculos matemáticos:\\
\\
$ T_{0} = 348,28 s$ (tiempo total)\\
\\
$ T_{s} = 348,27 s$ (tiempo en la funci\'on selection sort)\\
\\
$ T_{m} $ (tiempo mejorado)\\
\\
$ f = ? $ (\% de tiempo en la funci\'on selection sort)\\
\\
$ S_{g} = ?$ (Speedup global)\\
\\
$ S_{m} = ?$ (Speedup mejora)\\
\\
$ f = \frac{T_{s}}{T_{0}} = \frac{348,27}{348,28} = 0,99$ \\
\\
Aplicando la Ley de Amdahl:\\
\\
$S_{g} = \frac{T_{0}}{T_{m}}=\frac{1}{(1 - f) + \frac{f}{ S_{m}}}$\\ 
\\
${S_{g}}_{max}=\lim_{{S_{m}}\rightarrow {\infty}}{\frac{1}{(1 - f) + \frac{f}{ S_{m}}}}=1/0,01=100$\\
\\
Por lo tanto el SpeedUp máximo posible es 100.
\end{normalsize}\newpage

\newpage
\section{Conclusión}
\begin{normalsize}
La evaluación del desempeño de un sistema es un paso fundamental en la construcción del mismo.
El desempeño de un sistema no esta ligado únicamente al hardware, ya que pequeños cambios en el software pueden acarrear grandes cambios en la rapidez con la que se ejecutan las tareas.\\
Existen ciertas herramientas que permiten evaluar el desempeño del sistema en forma general y modular. Estas herramientas permiten hallar los puntos en los cuales hay que trabajar para lograr cambios significativos, así mismo permite descartar las áreas sobre las cuales no es beneficioso trabajar.
Dichas herramientas son matemáticas o software de prueba.\\
Un criterio correcto en el análisis de los datos obtenidos permite evaluar con certeza la situación actual del sistema y diseñar con eficacia las nuevas mejoras.\\
Así mismo el análisis permite conocer los límites teóricos del rendimiento obtenible con ciertas configuraciones.
\end{normalsize}
\newpage
\section{Anexo mediciones}
\begin{normalsize}
\end{normalsize}

\begin{figure}[hbtp]
\centering
\includegraphics[width=352pt , height=150pt]{mergeSort1.png} 
\caption{Merge Sort 100 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort2.png} 
\caption{Merge Sort 200 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort3.png} 
\caption{Merge Sort 400 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort4.png} 
\caption{Merge Sort 800 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort5.png} 
\caption{Merge Sort 1600 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort6.png} 
\caption{Merge Sort3200 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort7.png} 
\caption{Merge Sort 6400 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort8.png} 
\caption{Merge Sort12800 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort9.png} 
\caption{Merge Sort 25600 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort10.png} 
\caption{Merge Sort 51200 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort11.png} 
\caption{Merge Sort 102400 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort12.png} 
\caption{Merge Sort 204800 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort13.png} 
\caption{Merge Sort 409600 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort14.png} 
\caption{Merge Sort 819200 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort15.png} 
\caption{Merge Sort 1638400 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort16.png} 
\caption{Merge Sort 3276800 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{mergeSort17.png} 
\caption{Merge Sort 6553600 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort1.png} 
\caption{Selection Sort 100 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort2.png} 
\caption{Selection Sort 200 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort3.png} 
\caption{Selection Sort 400 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort4.png} 
\caption{Selection Sort 800 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort5.png} 
\caption{Selection Sort 1600 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort6.png} 
\caption{Selection Sort 3200 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort7.png} 
\caption{Selection Sort 6400 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort8.png} 
\caption{Selection Sort 12800 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort9.png} 
\caption{Selection Sort 25600 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort10.png} 
\caption{Selection Sort 51200 bytes}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort11.png} 
\caption{Selection Sort 102400 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort12.png} 
\caption{Selection Sort 204800 bytes}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort13.png} 
\caption{Selection Sort 409600 bytes}
\end{figure}

\newpage

\begin{figure}[hbtp]
\centering
\includegraphics[width=338pt , height=150pt]{selectionsort14.png} 
\caption{Selection Sort 819200 bytes}
\end{figure}

\newpage 

\section{Anexo Script}
\begin{small}
``medicion.sh''\linebreak 
\begin{lstlisting}
#! /bin/bash
#variables globales
let milisegundos=0
let real
let sys
let user
#obtencion de milisegundos de una linea
#El primer par\'ametro es la cadena que contiene el tiempo codificado
#como xxmyys.
#Se retorna la cantidad de milisegundos indicados por la l\'inea
function obtenerMilisegundos(){
	local cadena
	local cadenaAux
	local aux
	local pos
	cadena=$1
	miliSegundos=0
	pos=`expr index "$cadena" m`
	aux=`expr $pos - 1`
	cadenaAux=${cadena:0:aux}
	milisegundos=$cadenaAux
	milisegundos=`expr $milisegundos \* 60000`
	cadena=${cadena:pos}
	pos=`expr index "$cadena" .`
	aux=`expr $pos - 1`
	aux=${cadena:0:aux}
	aux=`expr $aux \* 1000`
	milisegundos=`expr $milisegundos + $aux`
	cadena=${cadena:pos}
	pos=`expr index "$cadena" s`
	aux=`expr $pos - 1`
	aux=${cadena:0:aux}
	milisegundos=`expr $milisegundos + $aux`
}	
#Se obtienen los tiempos de ordenamientos de c/archivo en milisegundos
function obtenerTiempos(){
	local linea
	local cadena
	local pos
	cadena=""
	linea=""
	while read linea
	do
		pos=`expr match "$linea" "real"`
		cero=0
		if [ $pos -ne $cero ]; then
			cadena=${linea:$pos}
			obtenerMilisegundos $cadena
			real=`expr $real + $milisegundos`
			
		else
			pos=`expr match "$linea" "user"`
			if [ $pos -ne $cero ]; then
				cadena=${linea:$pos}
				obtenerMilisegundos $cadena
				user=`expr $user + $milisegundos`
			else
				pos=`expr match "$linea" "sys"`
				if [ $pos -ne $cero ]; then
					cadena=${linea:$pos}
					obtenerMilisegundos $cadena
					sys=`expr $sys + $milisegundos`
				fi	
			fi
		fi
	done < "medicionIndividual.txt"
}
#C\'alculo tiempos promedios de ordenamiento para 10 archivos aleatorios sin 
#ordenar
#Parametros:
# 1: tamanio en bytes
# 2: cantidad de muestras por archivo
# 3: tipo de ordenamiento -m o -s
function 10archivosAleatoriosSinOrdenar(){
	local tamanio
	local realTotal=0
	local sysTotal=0
	local userTotal=0
	local i
	local divisor
	local muestras
	local tipoOrd
	tamanio=$1
	muestras=$2
	tipoOrd=$3
	# 10 archivos
	echo "Promedio de tiempos para 10 archivos aleatorios sin ordenar de $tamanio bytes, por m\'etodo $tipoOrd"
	echo "archivo 			 	real[ms]							user[ms]							sys[ms]"
	for i in {0..9} 
	do
		real=0
		sys=0
		user=0
		head -c $tamanio /dev/urandom >random.txt
		#Se toma una muestra de tamanio <muestras> para c/archivo
		for (( j=0; j<$muestras; j++ ))
		do
			echo -n "" >medicionIndividual.txt 
			echo -n "" >salida.txt
			time ./tp $tipoOrd random.txt >salida.txt 2>error.txt 
			obtenerTiempos
		done
		#Actualizaci\'on suma total
		realTotal=`expr $real + $realTotal`
		sysTotal=`expr $sys + $sysTotal`
		userTotal=`expr $user + $userTotal`
		#Promedio Parcial
		real=`expr $real / $muestras`
		sys=`expr $sys / $muestras`
		user=`expr $user / $muestras`
		echo "$i 						$real									$user 									$sys"
	done
	#Promedio Total
	divisor=`expr $muestras \* 10`
	realTotal=`expr $realTotal / $divisor`
	sysTotal=`expr $sysTotal / $divisor`
	userTotal=`expr $userTotal / $divisor`
	echo "Promedio Total			$realTotal									$userTotal 									$sysTotal"
	echo ""
}
#Medir tiempos archivo ordenado
#C\'alculo tiempos promedios de ordenamiento para un archivo aleatorio ordenado
#Parametros:
# 1: tamanio en bytes
# 2: cantidad de muestras por archivo
# 3: tipo de ordenamiento -m o -s
function tiempoArchivoOrdenado(){
	local tamanio
	local ruta
	local muestras
	local tipoOrd
	tamanio=$1
	muestras=$2
	tipoOrd=$3
	ruta="random.txt"
	#Un archivo ordenado
	echo "Promedio de tiempos para un archivo ordenado de $tamanio bytes, por m\'etodo $tipoOrd"
	echo "real[ms]							user[ms]							sys[ms]"
	real=0
	sys=0
	user=0
	./tp -m random.txt >randomOrdenado.txt 2>error.txt 
	#Se toma una muestra de tamanio <muestras> para c/archivo
	for (( j=0; j<$muestras; j++ ))
	do 
		#Se toma una muestra de tamanio <muestras> para c/archivo
		echo -n "" > medicionIndividual.txt
		echo -n "" > salida.txt
		time ./tp $tipoOrd randomOrdenado.txt >salida.txt 2>error.txt 
		obtenerTiempos
	done
	#Promedio
	real=`expr $real / $muestras`
	sys=`expr $sys / $muestras`
	user=`expr $user / $muestras`
	echo "$real									$user 									$sys"
	echo ""
}
#Medir tiempos archivo ordenado inverso
#C\'alculo tiempos promedios de ordenamiento para un archivo aleatorio ordenado inverso
#Parametros:
# 1: tamanio en bytes
# 2: cantidad de muestras por archivo
# 3: tipo de ordenamiento -m o -s
function tiempoArchivoOrdenadoInverso(){
	local tamanio
	local muestras
	local tipoOrd
	tamanio=$1
	muestras=$2
	tipoOrd=$3
	#Un archivo ordenado
	echo "Promedio de tiempos para un archivo con orden inverso de $tamanio bytes, por m\'etodo $tipoOrd"
	echo "real[ms]							user[ms]							sys[ms]"
	real=0
	sys=0
	user=0
	./tp -i random.txt >randomInverso.txt
	#Se toma una muestra de tamanio <muestras> para c/archivo
	for (( j=0; j<$muestras; j++ ))
	do 
		echo -n "" >medicionIndividual.txt
		echo -n "" >salida.txt
		#Se toma una muestra de tamanio <muestras> para c/archivo
		time ./tp $tipoOrd randomInverso.txt >salida.txt 2>error.txt 
		obtenerTiempos
	done
	#Promedio
	real=`expr $real / $muestras`
	sys=`expr $sys / $muestras`
	user=`expr $user / $muestras`
	echo "$real									$user 									$sys"
	echo ""
}
#Prueba completa para un tamanio en bytes dado.
#Las pruebas consisten en tomar los tiempos promedios para un archivo ordenado,
#un archivo ordenado inverso y 10 archivos totalmente aleatorios.
#Par\'ametros:
# 1: tamanio en bytes
# 2: tamanio de las muestras para calcular promedios individuales.
# 3: m\'etodo de ordenamiento a utilizar
# 4: tamanio de las muestras para el c\'alculo de tiempo de los archivos
#	 ordenados.
function tomarMediciones(){
	local tamanio
	local muestras
	local tipoOrd
	tamanio=$1
	muestras10=$2
	tipoOrd=$3
	muestrasOrd=$4	
	#Genero archivo random
	head -c $tamanio /dev/urandom >random.txt
	#Medir archivo ordenado
	tiempoArchivoOrdenado $tamanio $muestrasOrd $tipoOrd 
	#Medir archivo ordenado inverso
	tiempoArchivoOrdenadoInverso $tamanio $muestrasOrd $tipoOrd 
	#Medir 10 archivos
	10archivosAleatoriosSinOrdenar $tamanio $muestras10 $tipoOrd
}
#Programa Principal
#Parametros:
# 1: tamanio inicial en bytes 
# 2: tamanio final en bytes
# 3: tamanio de las muestras para calcular promedios de los 10 archivos
#    aleatorios.
# 4: tamanio de las muestras para el c\'alculo de tiempo de los archivos
#	 ordenados.
# 5: m\'etodo de ordenamiento a utilizar

echo "Mediciones"
i=$1
final=$2
muestras10=$3
muestrasOrd=$4
metodoOrd=$5
while [ $i -le $final ]
do
	tomarMediciones $i $muestras10 $metodoOrd $muestrasOrd
	i=`expr $i \* 2`
done

\end{lstlisting}
\newpage 
\end{small}
\section{Anexo c\'odigo fuente C}
\begin{lstlisting}
/*
 =========================================================
 Name        : tp06620.c
 Author      : rafaelputaro
 Version     : 1.0
 Description : Trabajo Pr\'actico 0 Organizaci\'on De Computadoras, Ansi-style
 =========================================================
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ProcesamientoArgumentos.h"

/*
 * Pre: "argc" es el n\'umero de elementos que contiene "argv".
 * "argv" es un vector con un conjunto de argumentos de entrada los cuales
 * pueden nombres de archivos u opciones dadas por el siguiente formato:
 * -h, --help
 * -V, --version
 * -m, --merge
 * -s, --sel
 * El primer par\'ametro es la opci\i'on, luego pueden ser las rutas de uno o
 * varios archivos en cualquier orden.
 * Post: Se ha operado de acuerdo a los par\'ametros.
 */
int main(int argc , char *argv[]) {
	unsigned char* vector;
	unsigned long int tamanio;
	vector = NULL;
	tamanio = 0;
	procesarArgumentos(argc , argv , &vector , &tamanio);
	if(vector != NULL) {
		free(vector);
	}
	return EXIT_SUCCESS;
}
/*
 * ProcesamientoArgumentos.h
 *
 *  Created on: 27/03/2012
 *      Author: putaro
 */

#ifndef PROCESAMIENTOARGUMENTOS_H_
#define PROCESAMIENTOARGUMENTOS_H_
#define HELP 'h'
#define VERSION 'v'
#define MERGESORT 'm'
#define SELECTIONSORT 's'
#define MERGESORTINVERSO 'i'
#define TAMANIO_MAXIMO_VECTOR 6553601
#define VERSION_PROGRAMA "1.0"

/*
 * Pre: "argc" es el n\'umero de elementos que contiene "argv".
 * "argv" es un vector con un conjunto de argumentos de entrada los cuales
 * pueden nombres de archivos u opciones dadas por el siguiente formato:
 * -h, --help
 * -V, --version
 * -m, --merge
 * -s, --sel
 * El primer par\'ametro es la opci\'on, luego pueden ser las rutas de uno o
 * varios archivos en cualquier orden.
 * En caso que el par\'ametro vector sea un puntero nulo se crear\'a el mismo.
 * Si el par\'ametro vector no es nulo se agregaran los datos nuevos al final
 * del mismo, siempre y cuando alcance la capacidad del vector.
 *
 * Post: Se han procesando los argumentos inicializando el vector par\'ametro
 * y su longitud.
 * NOTA: La destrucci\'on del vector queda a cargo del usuario.
 */
void procesarArgumentos(const int argc , char* const argv[] ,
					unsigned char** vector , unsigned long int* const tamanio);

#endif /* PROCESAMIENTOARGUMENTOS_H_ */

/*
 * ProcesamientoArgumentos.c
 *
 *  Created on: 27/03/2012
 *      Author: putaro
 */
#include "ProcesamientoArgumentos.h"
#include "Ordenamiento.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se imprimen todos los caracteres del vector por salida est\'andar.
 */
void imprimirVectorPorSalidaEstandar(unsigned char* vector ,
						const unsigned long int const tamanio );

/*
 * Pre: -
 * Post: Si la ruta del archivo es correcta se carga el contenido del mismo
 * en el vector y se retorna cualquier n\'umero distinto de cero.
 * Si la ruta del archivo es inv\'alida o nula y el vector esta vac\'io se
 * pedir\'a el ingreso de datos por teclado y se retorna cualquier n\'umero
 * distinto de cero.
 * En caso que el vector no este vac\'io y el archivo sea incorrecto o
 * nulo se retorna cero manteniendose el contenido previo del vector.
 *
 */
int procesarCargaDatos(const char* ruta , unsigned char** vector ,
						unsigned long int* const tamanio);

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Si coincide con alguna de las opciones correctas se modifica opcionSalida a
 * la misma y se retorna cualquier valor distinto de cero, caso contrario 0.
 */
int procesarOpciones(const char* opcionEntrada , char* const opcionSalida);

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Se han cargado datos desde el teclado en el vector par\'ametro.
 */
void cargarDatosDesdeStdin(unsigned char** vector ,
							unsigned long int* const tamanio);

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Se han cargado datos desde el archivo dado por el par\'ametro ruta.
 */
unsigned int cargarDatosDesdeArchivo(const char* ruta , unsigned char** vector ,
						unsigned long int* const tamanio);

/*
 * Pre: Los par\'ametros han sido correctamente inicializados.
 * Post: Se ejecuto la opcion en base al estado de los par\'ametros.
 */
int ejecutarOpcion(unsigned char** vector ,	unsigned long int* const tamanio ,
					const char opcion);

/*
 * Pre: "argc" es el numero de elementos que contiene "argv".
 * "argv" es un vector con un conjunto de argumentos de entrada los cuales
 * pueden nombres de archivos u opciones dadas por el siguiente formato:
 * -h, --help
 * -V, --version
 * -m, --merge
 * -s, --sel
 * El primer par\'ametro es la opci\'on, luego pueden ser las rutas de uno o
 * varios archivos en cualquier orden.
 * En caso que el par\'ametro vector sea un puntero nulo se crear\'a el mismo.
 * Si el par\'ametro vector no es nulo se agregaran los datos nuevos al final
 * del mismo, siempre y cuando alcance la capacidad del vector.
 *
 * Post: Se han procesando los argumentos inicializando el vector par\'ametro
 * y su longitud.
 * NOTA: La destrucci\'on del vector queda a cargo del usuario.
 */
void procesarArgumentos(const int argc , char* const argv[] ,
		unsigned char** vector , unsigned long int* const tamanio) {
	char opcion;
	*vector = NULL;
	*tamanio = 0;
	opcion = SELECTIONSORT; /* por defecto selection sort*/
	if(argc > 1) {
		if(argc == 2) {
			if(!procesarOpciones(argv[1] , &opcion)) {
				if ((opcion != HELP) && (opcion != VERSION))
					procesarCargaDatos(argv[1] , vector , tamanio);
			} else {
				if((opcion != HELP) && (opcion != VERSION)) {
					procesarCargaDatos(NULL , vector , tamanio);
				}
			}
		} else {
			unsigned int i;
			if(procesarOpciones(argv[1] , &opcion)) {
				i = 2;
			} else {
				i = 1;
			}
			if((opcion != HELP) && (opcion != VERSION)) {
				while(i < argc) {
					procesarCargaDatos(argv[i] , vector ,
									tamanio);
					i++;
				}
			}
		}
	} else {
		/* Si no hay opciones se cargan datos y se ordena por el m\'etodo
		 * Selection Sort*/
		procesarCargaDatos(NULL , vector , tamanio);
	}
	ejecutarOpcion(vector, tamanio , opcion);
}

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Si coincide con alguna de las opciones correctas se modifica opcionSalida a
 * la misma y se retorna cualquier valor distinto de cero, caso contrario 0.
 */
int procesarOpciones(const char* opcionEntrada , char* const opcionSalida) {
	int retorno = 0;
	if (opcionEntrada != NULL) {
		if((strlen(opcionEntrada) == 2)) {
			if(opcionEntrada[0] == '-') {
				switch (opcionEntrada[1]) {
					case HELP :	{
						*opcionSalida = HELP;
						retorno = 1;
						break;
					}
					case VERSION : {
						*opcionSalida = VERSION;
						retorno = 1;
						break;
					}
					case MERGESORT : {
						*opcionSalida = MERGESORT;
						retorno = 1;
						break;
					}
					case SELECTIONSORT : {
						*opcionSalida = SELECTIONSORT;
						retorno = 1;
						break;
					}
					case MERGESORTINVERSO : {
						*opcionSalida = MERGESORTINVERSO;
						retorno = 1;
						break;
					}
					default : {
						fprintf(stderr,"ERROR: Opci\'on inv\'alida.\n");
					}
				}
			}
		}
	}
	return retorno;
}

/*
 * Pre: -
 * Post: Si la ruta del archivo es correcta se carga el contenido del mismo
 * en el vector y se retorna cualquier n\'umero distinto de cero.
 * Si la ruta del archivo es inv\'alida o nula y el vector esta vac\'io se
 * pedir\'a el ingreso de datos por teclado y se retorna cualquier n\'umero
 * distinto de cero.
 * En caso que el vector no este vac\'io y el archivo sea incorrecto o
 * nulo se retorna cero manteniendose el contenido previo del vector.
 *
 */
int procesarCargaDatos(const char* ruta , unsigned char** const vector ,
						unsigned long int* const tamanio) {
	int retorno = 0;
	if(ruta != NULL) {
		if(strlen(ruta) > 0) {
			/* carga desde archivo*/
			retorno = cargarDatosDesdeArchivo(ruta , vector , tamanio);
		} else {
			/* carga desde stdin*/
			cargarDatosDesdeStdin(vector , tamanio);
			retorno = 1;
		}
	} else {
		if(*tamanio == 0) {
			/* carga desde stdin*/
			cargarDatosDesdeStdin(vector , tamanio);
			retorno = 1;
		}
	}
	return retorno;
}

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Se han cargado datos desde el teclado en el vector par\'ametro.
 */
void cargarDatosDesdeStdin(unsigned char** const vector ,
							unsigned long int* const tamanio) {
	int fin;
	unsigned char c;
	*vector =  malloc(sizeof(unsigned char) * TAMANIO_MAXIMO_VECTOR);
	memset(*vector , 0 , sizeof(unsigned char) * TAMANIO_MAXIMO_VECTOR);
	*tamanio = 0;
	fin = 0;
	c = '\n';
	while((!fin) && ((*tamanio) < TAMANIO_MAXIMO_VECTOR )) {
		int cantidad = 0;
		cantidad = scanf("%c" , &c);
		fin = (cantidad < 1) || (c == '\n');
		if(!fin) {
			(*vector)[*tamanio] = c;
			(*tamanio)++;
		}
	}
}

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Se han cargado datos desde el archivo dado por el par'ametro ruta.
 */
unsigned int cargarDatosDesdeArchivo(const char* ruta , unsigned char** vector ,
						unsigned long int* const tamanio) {
	int fin , retorno = 0;
	unsigned char c;
	FILE* file;
	file = fopen(ruta , "r");
	if(*vector == NULL) {
		*vector = malloc(sizeof(unsigned char) * TAMANIO_MAXIMO_VECTOR);
		memset(*vector , 0 , sizeof(unsigned char) * TAMANIO_MAXIMO_VECTOR);
		*tamanio = 0;
	}
	fin = (file == NULL);
	c = 0;
	while((!fin) && ((*tamanio) < TAMANIO_MAXIMO_VECTOR )) {
		int cantidad = 0;
		cantidad = fread(&c , sizeof(unsigned char) , 1 , file);
		if (cantidad > 0) {
			fin = feof(file);
			if(!fin) {
				(*vector)[*tamanio] = c;
				(*tamanio)++;
				retorno = 1;
			}
		} else {
			fin = 1;
		}
	}
	if(file != NULL) {
		fclose(file);
	} else {
		fprintf(stderr , "ERROR: No se encontro el archivo.\n");
	}
	return retorno;
}

/*
 * Pre: Los par\'ametros han sido correctamente inicializados.
 * Post: Se ejecuto la opcion en base al estado de los par\'ametros.
 */
int ejecutarOpcion(unsigned char** vector ,	unsigned long int* const tamanio ,
					const char opcion) {
	int retorno = 0;
	switch (opcion) {
		case HELP : {
			printf("tp0 [OPTIONS][file...]\n");
			printf("-h, --help			display	this help and exit.\n");
			printf("-v, --version		display version informaticon and exit.\n");
			printf("-m, --merge			use the mergesort algorithm.\n");
			printf("-s, --selection		use the selection sort algorithm. \n");
			retorno = 1;
			break;
		}
		case VERSION : {
			printf("%s\n",VERSION_PROGRAMA);
			retorno = 1;
			break;
		}
		case MERGESORT : {
			mergeSort(*vector , *tamanio);
			retorno = 1;
			imprimirVectorPorSalidaEstandar(*vector , *tamanio);
			break;
		}
		case MERGESORTINVERSO : {
			mergeSortInverso(*vector , *tamanio);
			retorno = 1;
			imprimirVectorPorSalidaEstandar(*vector , *tamanio);
			break;
		}
		case SELECTIONSORT : {
			selectionSort(*vector , *tamanio);
			retorno = 1;
			imprimirVectorPorSalidaEstandar(*vector , *tamanio);
			break;
		}
	}
	return retorno;
}

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se imprimen todos los caracteres del vector por salida est\'andar.
 */
void imprimirVectorPorSalidaEstandar(unsigned char* vector ,
						const unsigned long int tamanio ) {
	unsigned long int i;
	for(i = 0 ; i < tamanio ; i++) {
		putchar(vector[i]);
	}
}

/*
 * Ordenamiento.h
 *
 *  Created on: 27/03/2012
 *      Author: putaro
 */

#ifndef ORDENAMIENTO_H_
#define ORDENAMIENTO_H_

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Selection Sort.
 */
void selectionSort(unsigned char* const vector ,
					const unsigned long int tamanio);

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Merge Sort.
 */
void mergeSort(unsigned char* const vector , const unsigned long int tamanio);

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Merge Sort.
 */
void mergeSortInverso(unsigned char* const vector , const unsigned long int tamanio);

#endif /* ORDENAMIENTO_H_ */

/*
 * Ordenamiento.c
 *
 *  Created on: 27/03/2012
 *      Author: putaro
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Selection Sort.
 */
void selectionSort(unsigned char* const vector ,
					const unsigned long int tamanio) {
	unsigned long int i , minimo;
	for (i = 0 ; i < tamanio - 1 ; i++) {
	    unsigned long int j;
	    unsigned char aux;
		minimo = i;
	    for (j = i + 1 ; j < tamanio ; j++) {
	        if (toupper(vector[j]) < toupper(vector[minimo])) {
	            minimo = j;
	        }
	    }
	    aux = vector[i];
	    vector[i] = vector[minimo];
	    vector[minimo] = aux;
	}
}

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Se ha aplicado el algoritmo Merge a las entradas.
 */
void merge(unsigned char* const vector1, const unsigned long int tamanio1,
			unsigned char* const vector2, const unsigned long int tamanio2,
			unsigned char* const vector3) {
    long int x1 , x2 , x3;
    x1 = 0;
    x2 = 0;
    x3 = 0;
    while ((x1 < tamanio1) && (x2 < tamanio2)) {
        if (toupper(vector1[x1]) < toupper(vector2[x2])) {
            vector3[x3] = vector1[x1];
            x1++;
        } else {
            vector3[x3] = vector2[x2];
            x2++;
        }
        x3++;
    }
    while (x1 < tamanio1) {
        vector3[x3] = vector1[x1];
        x1++;
        x3++;
    }
    while (x2 < tamanio2) {
        vector3[x3] = vector2[x2];
        x2++;
        x3++;
    }
}

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Merge Sort.
 */
void mergeSort(unsigned char* const vector , const unsigned long int tamanio) {
	unsigned char *vector1 , *vector2;
	unsigned long int tamanio1 , tamanio2;
    int x , y;
    if (tamanio > 1) {
        if ((tamanio % 2) == 0)
            tamanio1 = tamanio2 = (unsigned long int) (tamanio / 2);
        else {
            tamanio1 = (unsigned long int) (tamanio / 2);
            tamanio2 = tamanio1 + 1;
        }
        vector1 = malloc(sizeof(unsigned char) * tamanio1);
        vector2 = malloc(sizeof(unsigned char) * tamanio2);
        for (x = 0 ; x < tamanio1 ; x++)
            vector1[x] = vector[x];
        for (y = 0 ; y < tamanio2 ; x++ , y++)
            vector2[y] = vector[x];
        mergeSort(vector1 , tamanio1);
        mergeSort(vector2 , tamanio2);
        merge(vector1 , tamanio1 , vector2 , tamanio2 , vector);
        free(vector1);
        free(vector2);
    }
}

/*
 * Pre: Los par\'ametros son no nulos.
 * Post: Se ha aplicado el algoritmo Merge a las entradas.
 */
void mergeInverso(unsigned char* const vector1, const unsigned long int tamanio1,
			unsigned char* const vector2, const unsigned long int tamanio2,
			unsigned char* const vector3) {
    long int x1 , x2 , x3;
    x1 = 0;
    x2 = 0;
    x3 = 0;
    while ((x1 < tamanio1) && (x2 < tamanio2)) {
        if (toupper(vector1[x1]) > toupper(vector2[x2])) {
            vector3[x3] = vector1[x1];
            x1++;
        } else {
            vector3[x3] = vector2[x2];
            x2++;
        }
        x3++;
    }
    while (x1 < tamanio1) {
        vector3[x3] = vector1[x1];
        x1++;
        x3++;
    }
    while (x2 < tamanio2) {
        vector3[x3] = vector2[x2];
        x2++;
        x3++;
    }
}

/*
 * Pre: El par\'ametro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Merge Sort.
 */
void mergeSortInverso(unsigned char* const vector , const unsigned long int tamanio) {
	unsigned char *vector1 , *vector2;
	unsigned long int tamanio1 , tamanio2;
	int x , y;
	if (tamanio > 1) {
		if ((tamanio % 2) == 0)
			tamanio1 = tamanio2 = (unsigned long int) (tamanio / 2);
	    else {
	        tamanio1 = (unsigned long int) (tamanio / 2);
	        tamanio2 = tamanio1 + 1;
	    }
	    vector1 = malloc(sizeof(unsigned char) * tamanio1);
	    vector2 = malloc(sizeof(unsigned char) * tamanio2);
	    for (x = 0 ; x < tamanio1 ; x++)
	        vector1[x] = vector[x];
	    for (y = 0 ; y < tamanio2 ; x++ , y++)
	        vector2[y] = vector[x];
	    mergeSortInverso(vector1 , tamanio1);
	    mergeSortInverso(vector2 , tamanio2);
	    mergeInverso(vector1 , tamanio1 , vector2 , tamanio2 , vector);
	    free(vector1);
	    free(vector2);
	}
}
\end{lstlisting}
\newpage 
\section{Anexo c\'alculo de incertidumbres}
\begin{normalsize}
Para el cálculo de los tiempos promedios se utilizó la siguiente fórmula:\\
\\
$\overline{X}=\frac{\sum_{\forall n}{t_{i}}}{n}$ \\

La incertidumbre de una suma es la suma de las incertidumbres de los t\'erminos sumados por lo tanto:\\
\\
$\triangle X = n * \frac{\triangle t}{n} = \triangle t$ \\

Como la mínima lectura que arroja la función ``times'' es un milisegundo consideró que la incertidumbre de dicha función es la mitad de este valor, es decir medio milisegundo, por lo tanto:\\
\\
$\triangle X =0,5 ms $
\end{normalsize}
\newpage
\section{Biblografía}
\begin{thebibliography}{XXX}
\bibitem{Cer} Patterson David A., John L.  Hennessy, San Mateo, Computer Architecture a Quantitative Approach, 
\bibitem{Thin} Bruce Eckel, Thinking in C++
\bibitem{Font} Carlos Fontela, Orientación a objetos con Java y UML.
\end{thebibliography}

\end{document}